<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Built-in Constraints
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial056.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial053.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial058.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc118">8.4</A>&nbsp;&nbsp;Built-in Constraints</H2>
<A NAME="icbics"></A>
The following section summarises the built-in constraint predicates of the
<EM>ic</EM> library.<BR>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description"><A HREF="../bips/lib/ic/NN-2.html"><B>Vars :: Domain</B></A><A NAME="@default182"></A><DD CLASS="dd-description"> 
Constrains Vars to take only integer or real values from the domain
specified by Domain. Vars may be a variable, a list, or a submatrix (e.g.
M[1..4, 3..6]); for a list or a submatrix, the domain is applied recursively
so that one can apply a domain to, for instance, a list of lists of
variables. Domain can be specified as a simple range Lo .. Hi, or as a list
of subranges and/or individual elements (integer variables only). The type
of the bounds determines the type of the variable (real or integer). Also
allowed are the (untyped) symbolic bound values <TT>inf</TT>, <TT>+inf</TT> and
<TT>-inf</TT>.<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/ic/SNN-2.html"><B>Vars $:: Domain</B></A><A NAME="@default183"></A><DD CLASS="dd-description"> 
Like <TT>::/2</TT>, but for declaring real variables (i.e. it never imposes
integrality, regardless of the types of the bounds).<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/ic/HNN-2.html"><B>Vars #:: Domain</B></A><A NAME="@default184"></A><DD CLASS="dd-description"> 
Like <TT>::/2</TT>, but for declaring integer variables.<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/ic/reals-1.html"><B>reals(Vars)</B></A><A NAME="@default185"></A><DD CLASS="dd-description">
Declares that the variables are IC variables (like declaring
<TT>Vars :: -inf..inf</TT>).<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/ic/integers-1.html"><B>integers(Vars)</B></A><A NAME="@default186"></A><DD CLASS="dd-description"> 
Constrains the given variables to take integer values only.</DL>

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 8.1: Domain constraints</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
The most common way to declare an IC variable is to use the
<A HREF="../bips/lib/ic/NN-2.html"><B>::/2</B></A><A NAME="@default187"></A> predicate (or
<A HREF="../bips/lib/ic/SNN-2.html"><B>$::/2</B></A><A NAME="@default188"></A> or
<A HREF="../bips/lib/ic/HNN-2.html"><B>#::/2</B></A><A NAME="@default189"></A>) to give it an
initial domain:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- X :: -10 .. 10.
X = X{-10 .. 10}
Yes

?- X :: -10.0 .. 10.0.
X = X{-10.0 .. 10.0}
Yes

?- X #:: -10 .. 10.
X = X{-10 .. 10}
Yes

?- X $:: -10 .. 10.
X = X{-10.0 .. 10.0}
Yes

?- X :: 0 .. 1.0Inf.
X = X{0 .. 1.0Inf}
Yes

?- X :: 0.0 .. 1.0Inf.
X = X{0.0 .. 1.0Inf}
Yes

?- X :: [1, 4 .. 6, 9, 10].
X = X{[1, 4 .. 6, 9, 10]}
Yes
</PRE></BLOCKQUOTE>
Note that for <A HREF="../bips/lib/ic/NN-2.html"><B>::/2</B></A><A NAME="@default190"></A> the type
of the bounds defines the type of the variable (integer or real) but that
infinities are considered type-neutral. To just declare the type of a
variable without restricting the domain at all, one can use the
<A HREF="../bips/lib/ic/integers-1.html"><B>integers/1</B></A><A NAME="@default191"></A>
and <A HREF="../bips/lib/ic/reals-1.html"><B>reals/1</B></A><A NAME="@default192"></A>.<BR>
<BR>
The final way to declare that a variable is an IC variable is to just use it
in an IC constraint: this performs an implicit declaration.<BR>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description"><A HREF="../bips/lib/ic/HE-2.html"><B>ExprX #= ExprY</B></A><A NAME="@default193"></A><DD CLASS="dd-description">
ExprX is equal to ExprY. ExprX and ExprY are integer expressions, and the
variables and subexpressions are constrained to be integers.<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/ic/HGE-2.html"><B>ExprX #&gt;= ExprY</B></A><A NAME="@default194"></A><DD CLASS="dd-description">
ExprX is greater than or equal to ExprY. ExprX and ExprY are integer
expressions, and the variables and subexpressions are constrained to be
integers.<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/ic/HEL-2.html"><B>ExprX #=&lt; ExprY</B></A><A NAME="@default195"></A><DD CLASS="dd-description">
ExprX is less than or equal to ExprY. ExprX and ExprY are integer
expressions, and the variables and subexpressions are constrained to be
integers.<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/ic/HG-2.html"><B>ExprX #&gt; ExprY</B></A><A NAME="@default196"></A><DD CLASS="dd-description">
ExprX is greater than ExprY. ExprX and ExprY are integer expressions, and
the variables and subexpressions are constrained to be integers.<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/ic/HL-2.html"><B>ExprX #&lt; ExprY</B></A><A NAME="@default197"></A><DD CLASS="dd-description">
ExprX is less than ExprY. ExprX and ExprY are integer expressions, and the
variables and subexpressions are constrained to be integers.<BR>
<BR>
<DT CLASS="dt-description"><B>ExprX #\= ExprY</B><DD CLASS="dd-description">
ExprX is not equal to ExprY. ExprX and ExprY are integer
expressions, and the variables are constrained to be integers.<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/ic/ac_eq-3.html"><B>ac_eq(X, Y, C)</B></A><A NAME="@default198"></A><DD CLASS="dd-description">
Arc-consistent implementation of <B>X #= Y + C</B>. X and Y are
constrained to be integer variables and to have &#8220;reasonable&#8221; bounds. C
must be an integer.</DL>

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 8.2: Integral Arithmetic constraints<A NAME="integer-constraints"></A></DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<A NAME="@default199"></A>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description"><A HREF="../bips/lib/ic/SE-2.html"><B>ExprX $= ExprY</B></A><A NAME="@default200"></A><DD CLASS="dd-description">
ExprX is equal to ExprY. ExprX and ExprY are general expressions.<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/ic/SGE-2.html"><B>ExprX $&gt;= ExprY</B></A><A NAME="@default201"></A><DD CLASS="dd-description">
ExprX is greater than or equal to ExprY. ExprX and ExprY are general
expressions.<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/ic/SEL-2.html"><B>ExprX $=&lt; ExprY</B></A><A NAME="@default202"></A><DD CLASS="dd-description">
ExprX is less than or equal to ExprY. ExprX and ExprY are general expressions.<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/ic/SG-2.html"><B>ExprX $&gt; ExprY</B></A><A NAME="@default203"></A><DD CLASS="dd-description">
ExprX is greater than ExprY. ExprX and ExprY are general expressions.<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/ic/SL-2.html"><B>ExprX $&lt; ExprY</B></A><A NAME="@default204"></A><DD CLASS="dd-description">
ExprX is less than ExprY. ExprX and ExprY are general expressions.<BR>
<BR>
<DT CLASS="dt-description"><B>ExprX $\= ExprY</B><DD CLASS="dd-description">
ExprX is not equal to ExprY. ExprX and ExprY are general expressions.
</DL>
	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 8.3: Non-Integral Arithmetic Constraints<A NAME="general-constraints"></A></DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<A NAME="@default205"></A>
The basic IC relational constraints come in two forms. The first form is
for integer-only constraints, and is summarised in
Figure&nbsp;<A HREF="#integer-constraints">8.2</A>. All of these constraints contain
<TT>#</TT> in their name, which indicates that all numbers appearing in
them must be integers, and all variables <EM>and subexpressions</EM> will be
constrained to be integral. It is important to note that subexpressions are
constrained to be integral, because it means, for instance, that
<B>X/2 + Y/2 #= 1</B> and <B>X + Y #= 2</B> are different
constraints, since the former constrains X and Y to be even.<BR>
<BR>
The second form is the general form of the constraints, and is summarised in
Figure&nbsp;<A HREF="#general-constraints">8.3</A>. These constraints can be used with either
integer or real variables and numbers. With the exception of integrality
issues, the two versions of each constraint are equivalent. Thus if the
constants are integers and the variables and subexpressions are integral,
the two forms may be used interchangeably.<BR>
<BR>
Most of the basic constraints operate by propagating bound information
(performing interval reasoning). The exceptions are the disequality (not
equals) constraints and the <B>ac_eq/3</B> constraint, which perform
domain reasoning (arc consistency). An example:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- [X, Y] :: 0 .. 10, X #&gt;= Y + 2.
X = X{2 .. 10}
Y = Y{0 .. 8}
There is 1 delayed goal.
Yes
</PRE></BLOCKQUOTE>
In the above example, since the lower bound of <TT>Y</TT> is 0 and
<TT>X</TT> must be at least 2 greater, the lower bound of <TT>X</TT> has
been updated to 2. Similarly, the upper bound of <TT>Y</TT> has been
reduced to 8. The delayed goal indicates that the constraint is still
active: there are still some combinations of values for <TT>X</TT> and
<TT>Y</TT> which violate the constraint, so the constraint remains until it
is sure that no such violation is possible.<BR>
<BR>
Note that if a domain ever becomes empty as the result of propagation (no
value for the variable is feasible) then the constraint must necessarily
have been violated, and the computation backtracks.<BR>
<BR>
For a disequality constraint, no deductions can be made until
there is only one variable left, at which point (if it is an integer
variable) the variable's domain can be updated to exclude the relevant
value:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- X :: 0 .. 10, X #\= 3.
X = X{[0 .. 2, 4 .. 10]}
Yes

?- [X, Y] :: 0 .. 10, X - Y #\= 3.
X = X{0 .. 10}
Y = Y{0 .. 10}
There is 1 delayed goal.
Yes

?- [X, Y] :: 0 .. 10, X - Y #\= 3, Y = 2.
X = X{[0 .. 4, 6 .. 10]}
Y = 2
Yes
</PRE></BLOCKQUOTE>
For the <A HREF="../bips/lib/ic/ac_eq-3.html"><B>ac_eq/3</B></A><A NAME="@default206"></A> constraint, &#8220;holes&#8221;
in the domain of one variable are propagated to the other:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- [X, Y] :: 0 .. 10, ac_eq(X, Y, 3).
X = X{3 .. 10}
Y = Y{0 .. 7}
There is 1 delayed goal.
Yes

?- [X, Y] :: 0 .. 10, ac_eq(X, Y, 3), Y #\= 4.
X = X{[3 .. 6, 8 .. 10]}
Y = Y{[0 .. 3, 5 .. 7]}
There is 1 delayed goal.
Yes
</PRE></BLOCKQUOTE>
Compare with the corresponding bounds consistency constraint:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- [X, Y] :: 0 .. 10, X #= Y + 3, Y #\= 4.
X = X{3 .. 10}
Y = Y{[0 .. 3, 5 .. 7]}
There is 1 delayed goal.
Yes
</PRE></BLOCKQUOTE>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&#8857;</B><DD CLASS="dd-description"> <FONT COLOR="#9832CC">IC supports a range of mathematical operators beyond the basic
<TT>+/2</TT></FONT><FONT COLOR="#9832CC">, <TT>-/2</TT></FONT><FONT COLOR="#9832CC">, <TT>*/2</TT></FONT><FONT COLOR="#9832CC">, etc. See the IC chapter in
the Constraint Library Manual for full details.</FONT>
</DL>


<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCFFCC">
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&otimes;</B><DD CLASS="dd-description"> If one wishes to construct an expression to use in an IC constraint at
run time, then one must wrap it in <TT>eval/1</TT>:
</DL>
</TD>
</TR></TABLE>

<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- [X, Y] :: 0..10, Expr = X + Y, Sum #= Expr.
number expected in set_up_ic_con(7, 1, [0 * 1, 1 * Sum{-1.0Inf .. 1.0Inf}, -1 * (X{0 .. 10} + Y{0 .. 10})])
Abort

?- [X, Y] :: 0..10, Expr = X + Y, Sum #= eval(Expr).
X = X{0 .. 10}
Y = Y{0 .. 10}
Sum = Sum{0 .. 20}
Expr = X{0 .. 10} + Y{0 .. 10}
There is 1 delayed goal.
Yes
</PRE></BLOCKQUOTE>
<EM>Reification</EM> provides access to the logical truth of a constraint
expression and can be used by:
<UL CLASS="itemize"><LI CLASS="li-itemize">
The ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> system to infer the truth value, reflecting the value 
into a variable.
<LI CLASS="li-itemize">The programmer to enforce the constraint or its negation by giving a
value to the truth variable.
</UL>
This logical truth value is a boolean variable (domain <TT>0..1</TT>), where
the value 1 means the constraint is or is required to be true, and the value
0 means the constraint is or is required to be false.<BR>
<BR>
When constraints appear in an expression context, 
they evaluate to their reified truth value. Practically, this means that 
the constraints are posted in a passive check but do not propagate mode.
In this mode no variable domains are modified but checks are made to
determine whether the constraint has become entailed (necessarily true) or 
disentailed (necessarily false).<BR>
<BR>
The simplest and arguably most natural way to reify a constraint is to
place it in an expression context (i.e. on either side of a <CODE>$=</CODE>,
<CODE>#=</CODE>, etc.) and assign its truth value to a variable. For example:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- X :: 0 .. 10, TruthValue $= (X $&gt; 4).
TruthValue = TruthValue{[0, 1]}
X = X{0 .. 10}
There is 1 delayed goal.
Yes

?- X :: 6 .. 10, TruthValue $= (X $&gt; 4).
TruthValue = 1
X = X{6 .. 10}
Yes

?- X :: 0 .. 4, TruthValue $= (X $&gt; 4).
TruthValue = 0
X = X{0 .. 4}
Yes
</PRE></BLOCKQUOTE>
All the basic relational constraint predicates also come in a three-argument
form where the third argument is the reified truth value, and this form can
also be used to reify a constraint directly. For example:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- X :: 0 .. 10, $&gt;(X, 4, TruthValue).
X = X{0 .. 10}
TruthValue = TruthValue{[0, 1]}
There is 1 delayed goal.
Yes
</PRE></BLOCKQUOTE>
As noted above the boolean truth variable corresponding to a constraint can
also be used to enforce the constraint (or its negation):
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- X :: 0 .. 10, TruthValue $= (X $&gt; 4), TruthValue = 1.
X = X{5 .. 10}
TruthValue = 1
Yes

?- X :: 0 .. 10, TruthValue $= (X $&gt; 4), TruthValue = 0.
X = X{0 .. 4}
TruthValue = 0
Yes
</PRE></BLOCKQUOTE>
By instantiating the value of the reified truth variable, the constraint
changes from being <EM>passive</EM> to being <EM>active</EM>. Once actively
true (or actively false) the constraint will prune domains as though
it had been posted as a simple non-reified constraint.
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&#8857;</B><DD CLASS="dd-description"> <FONT COLOR="#9832CC">Additional information on reified constraints can be found in the
ECL</FONT><SUP><FONT COLOR="#9832CC"><I>i</I></FONT></SUP><FONT COLOR="#9832CC">PS</FONT><SUP><FONT COLOR="#9832CC"><I>e</I></FONT></SUP><FONT COLOR="#9832CC"> Constraint Library Manual that documents <EM>IC: A Hybrid
 Finite Domain / Real Number Interval Constraint Solver</EM>.</FONT>
</DL>


	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description"><B>and</B><DD CLASS="dd-description">
 Constraint conjunction. e.g. <TT>X $&gt; 3 and X $&lt; 8</TT><BR>
<BR>
<DT CLASS="dt-description"><B>or</B><DD CLASS="dd-description">
 Constraint disjunction. e.g. <TT>X $&lt; 3 or X $&gt; 8</TT><BR>
<BR>
<DT CLASS="dt-description"><B>=&gt;</B><DD CLASS="dd-description">
 Constraint implication. e.g. <TT>X $&gt; 3 =&gt; Y $&lt; 8</TT><BR>
<BR>
<DT CLASS="dt-description"><B>neg</B><DD CLASS="dd-description">
 Constraint negation. e.g. <TT>neg X $&gt; 3</TT></DL>

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 8.4: Constraint Expression Connectives<A NAME="expression-connectives"></A></DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
IC also provides a number of connectives useful for combining constraint
expressions. These are summarised in Figure&nbsp;<A HREF="#expression-connectives">8.4</A>.
For example:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- [X, Y] :: 0 .. 10, X #&gt;= Y + 6 or X #=&lt; Y - 6.
X = X{0 .. 10}
Y = Y{0 .. 10}
There are 3 delayed goals.
Yes

?- [X, Y] :: 0 .. 10, X #&gt;= Y + 6 or X #=&lt; Y - 6, X #&gt;= 5.
Y = Y{0 .. 4}
X = X{6 .. 10}
There is 1 delayed goal.
Yes
</PRE></BLOCKQUOTE>
In the above example, once it is known that <TT>X #=&lt; Y - 6</TT> cannot be
true, the constraint <TT>X #&gt;= Y + 6</TT> is enforced.<BR>
<BR>
Note that these connectives exploit constraint reification, and actually
just reason about boolean variables. This means that they can be used as
boolean constraints as well:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- A =&gt; B.
A = A{[0, 1]}
B = B{[0, 1]}
There is 1 delayed goal.
Yes

?- A =&gt; B, A = 1.
B = 1
A = 1
Yes

?- A =&gt; B, A = 0.
B = B{[0, 1]}
A = 0
Yes
</PRE></BLOCKQUOTE>
<HR>
<A HREF="tutorial056.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial053.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial058.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
